package acm.test;

import java.util.ArrayList;
import java.util.List;

public class 直线交点 {
    public static void main(String[] args) {
        for (int i = 0; i <= 20; i++) {
            List<Integer> fun1 = fun1(i);
            List<Integer> answer = answer(i);
            if (!fun1.equals(answer)){
                System.out.println(i);
                System.out.println("预期输出："+answer.toString());
                System.out.println("实际输出："+fun1.toString());
            }
        }
    }
    public static List<Integer> fun1(int n){
        List<Integer> list=new ArrayList<>();
        int Sn=(n)*(n-1)/2;
        list.add(0);
        for (int i = 1; i < n; i++) {   //有多少条斜线
            int Si=Sn-(n-i)*(n-i-1)/2;
            list.add(Si);
        }
        return list;
    }

    //标准解
    public static List<Integer> answer(int n) {
        int[][] a = new int[22][220];
        List<Integer> list=new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            a[i][0] = 1;
            for (int j = 1; j < i; j++) {
                for (int k = 0; k <= j * (j - 1) / 2; k++) {
                    if (a[j][k] == 1) {
                        a[i][(i - j) * j + k] = 1;
                    }
                }
            }
        }
        list.add(0);
        for (int i = 1; i <= n * (n - 1) / 2; i++) {
            if (a[n][i] == 1) {
                list.add(i);
            }
        }
        return list;
    }
}
